% Francesco Cotto
% Data: 17/06/2009
%
% Soluzione problema regine
%

regina(L,C) :- number(L),number(C), L>0, C>0.

soluzione(S):- s_linee(S), s_colonne(S), s_diagonali_crescenti(S), s_diagonali_decrescenti(S).

s_linee([]).
s_linee([regina(L1,C1)|T]) :- s_linee_aux(regina(L1,C1), T), s_linee(T).

s_linee_aux(regina(_,_), []).
s_linee_aux(regina(L1,_),[regina(L2,_)|T]) :- L1 =:= L2, s_linee_aux(regina(L1,_),T).

s_colonne([]).
s_colonne([regina(L1,C1)|T]) :- s_colonne_aux(regina(L1,C1), T), s_colonne(T).

s_colonne_aux(regina(_,_), []).
s_colonne_aux(regina(_,C1),[regina(_,C2)|T]) :- C1 =\= C2, s_colonne_aux(regina(_,C1),T).

s_diagonali_crescenti([]).
s_diagonali_crescenti([regina(L1,C1)|T]) :- s_diag_cr_aux(regina(L1,C1), T),s_diagonali_crescenti(T).

s_diag_cr_aux(regina(_,_), []).
s_diag_cr_aux(regina(L1,C1), [regina(L2,C2)|T]) :- D1 is L1+C1, D2 is L2+C2, D1 =\= D2, s_diag_cr_aux(regina(L1,C1), T).

s_diagonali_decrescenti([]).
s_diagonali_decrescenti([regina(L1,C1)|T]) :- s_diag_decr_aux(regina(L1,C1), T),s_diagonali_decrescenti(T).

s_diag_decr_aux(regina(_,_), []).
s_diag_decr_aux(regina(L1,C1), [regina(L2,C2)|T]) :- D1 is L1-C1, D2 is L2-C2, D1 =\= D2, s_diag_decr_aux(regina(L1,C1), T).


%true soluzione([regina(1,2),regina(2,4),regina(3,1),regina(4,3)]).
%true soluzione([regina(1,2),regina(2,4),regina(3,1),regina(4,3),regina(5,5)]).

ordina_soluzione(S, OS) :- sort(S, OS).

regine(N) :- N>0, cerca_soluzione(N,1,[]).
cerca_soluzione(N,RC,S) :- RC>N, ordina_soluzione(S,OS), stampa_soluzione(OS).
cerca_soluzione(N,RC,S) :- cerca_soluzione_aux(N,regina(RC,1),S,NS), NRC is RC+1, cerca_soluzione(N,NRC,NS).

%cerca_soluzione_aux(DimensioneScacchiera, regina da aggiungere, soluzione, nuova soluzione)
%prova dalla prima colonna della linea su cui si trova la regina fino all'ultima.
cerca_soluzione_aux(N,regina(_,C),_,_) :- C>N, !, fail.
cerca_soluzione_aux(_,regina(L,C),S,NS) :- NS = [regina(L,C)|S], soluzione(NS).
cerca_soluzione_aux(N,regina(L,C),S,NS) :- NC is C+1, cerca_soluzione_aux(N,regina(L,NC),S,NS).

stampa_soluzione(S) :- write(S).

%esempi di query: setof(regine(5)).
%regine(3).